/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/single-number-iii
   @Language: C++
   @Datetime: 16-02-09 08:34
   */

class Solution {
public:
	/**
	 * @param A : An integer array
	 * @return : Two integers
	 * Tip: Asume a and b are answers, then a^b must not be 0.
	 *      We find last bit(also can find first bit) which is 1
	 *      and consider it as a, the other is b.
	 *      XOR all nums, except its bit is not 1.
	 *      At last, found the num a. (b=a^res)
	 */
	vector<int> singleNumberIII(vector<int> &A) {
		// write your code here
		int res=0, bit=0, ans=0, i;
		for(i=A.size(); i; res^=A[--i]);
		bit = res&(-res);
		for(i=A.size(); i--;)
			A[i]&bit ? ans^=A[i] : 0;
		return {ans,ans^res};
	}
};
